#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>

/*
迭代器失效问题
1. 迭代器为什么会失效
a.
当容器调用erase方法后，当前位置到容器末尾元素的所有迭代器全部失效了(删除元素时，后继元素相应往前填充，所以继续it++会遗漏部分元素)
b. 当容器调用insert方法后，当前位置到容器末尾元素的所有迭代器全部失效了
c. insert后，引起容器内存扩容，所有迭代器均失效

2. 迭代器失效了该如何处理
对插入删除点的迭代器进行更新操作  it=v.erase(it);

*/
int main() {
    std::vector<int> v;
    /* srand(static_cast<unsigned>(time(0))); */
    srand(42);
    for (size_t i = 0; i < 10; ++i) {
        v.push_back(rand() % 100 + 1);
    }
    std::vector<int> v2{v};
    std::cout << "原始数组元素：" << std::endl;
    for (auto i : v) {
        std::cout << i << " ";  // 67 41 82 42 13 59 22 41 36 44
    }
    std::cout << std::endl;

    // 以下代码中，在用迭代器遍历容器的同时，还对容器进行删除元素操作，迭代器会失效！！！导致遗漏部分元素！！！
    for (auto it = v.begin(); it != v.end(); ++it) {
        if (*it % 2 == 0) {
            v.erase(it);
        }
    }

    std::cout << "删除之后的元素（迭代器失效）：" << std::endl;
    for (auto i : v) {
        std::cout << i << " ";  // 67 41 42 13 59 41 44
    }
    std::cout << std::endl;

    // 正确的删除元素操作
    auto it = v2.begin();
    while (it != v2.end()) {
        if (*it % 2 == 0) {
            it = v2.erase(it);  // erase函数会返回下一个有效元素的迭代器
        } else {
            ++it;
        }
    }

    std::cout << "删除之后的元素（迭代器未失效）：" << std::endl;
    for (auto i : v2) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
    std::cout << "=====================================" << std::endl;

#if 0
    // 以下代码中，
    // 在用迭代器遍历容器的时候，还对容器进行插入元素操作，迭代器会失效！！！
    // 可能会引起vector容器内存扩容，所有迭代器均失效，也可能内存足够，但是一直重复访问相同元素，直到出现内存扩容，然后未定义行为！
    for (auto it = v2.begin(); it != v2.end(); ++it) {
        if (*it % 2 == 1) {
            v2.insert(it, *it - 1);
        }
    }

    std::cout << "插入之后的元素（迭代器失效）：" << std::endl;
    for (auto i : v2) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
#endif

    // 以下代码是正确的插入元素步骤
    std::vector<int> v3;
    for (auto i : v2) {
        if (i % 2 == 1) {
            v3.push_back(i - 1);
        }
        v3.push_back(i);
    }
    std::cout << "插入之后的元素（迭代器未失效）：" << std::endl;
    for (auto i : v3) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    // 正确插入元素的另一种办法
    for (auto it = v2.begin(); it != v2.end(); ++it) {
        if (*it % 2 == 1) {
            it = v2.insert(it, *it - 1);
            ++it;
        }
    }
    for (auto i : v2) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}
